package features.advance.leetcode.array.medium;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author LIN
 * @date 2021-04-27
 */
public class Solution16 {
        public int threeSumClosest1(int[] nums, int target) {
            Arrays.sort(nums);
            int result = nums[0] + nums[1] + nums[2];
            for(int i=0;i<nums.length-2;i++){
                if(i > 0 && nums[i] == nums[i-1]){
                    continue;
                }
                int left = i+1;
                int right = nums.length - 1;
                while(left != right){
                    int min = nums[i] + nums[left] + nums[left + 1];
                    if(target < min){
                        if(Math.abs(result - target) > Math.abs(min - target))
                            result = min;
                        break;
                    }
                    int max = nums[i] + nums[right] + nums[right - 1];
                    if(target > max){
                        if(Math.abs(result - target) > Math.abs(max - target))
                            result = max;
                        break;
                    }
                    int sum = nums[i] + nums[left] + nums[right];
                    // 判断三数之和是否等于target
                    if(sum == target)
                        return sum;
                    if(Math.abs(sum - target) < Math.abs(result - target))
                        result = sum;
                    if(sum > target){
                        right--;
                        while(left != right && nums[right] == nums[right+1])
                            right--;
                    }
                    else{
                        left++;
                        while(left != right && nums[left] == nums[left-1])
                            left++;
                    }
                }
            }
            return result;
        }

    public int threeSumClosest(int[] nums, int target){
        if(nums.length == 3){
            return nums[0]+nums[1]+nums[2];
        }
        int n = nums.length,ans=nums[0]+nums[1]+nums[2];
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        int first = 0;
        for(first=0;first<n;first++) {
            int third = n - 1;
            if (nums[first] >= target && first+2<n) {
                int sum = nums[first] + nums[first+1] + nums[first+2];
                int a = sum - target;
                ans = (ans - target > 0?ans - target:target - ans) >(a>0?a:0-a)?sum:ans;
                List list = new LinkedList();
                list.add(nums[first]);
                list.add(nums[first+1]);
                list.add(nums[first+2]);
                System.out.println(list);
                if(nums[first+1] < 0){
                    break;
                }
            }
            for (int second = first + 1; second < n; second++) {
                while (second < third && nums[third] + nums[second] + nums[first] > target) {
                    if (second < (third - 1) && nums[third - 1] + nums[second] + nums[first] <= target) {
                        int sum = nums[first] + nums[second] + nums[third];
                        int a = sum - target;
                        ans = (ans - target > 0?ans - target:target - ans) >(a>0?a:0-a)?sum:ans;

                        List list = new LinkedList();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        System.out.println(list);
                    } else {
                        List list = new LinkedList();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        System.out.println(list);
                        int sum = nums[first] + nums[second] + nums[third];
                        int a = sum - target;
                        ans = (ans - target > 0?ans - target:target - ans) >(a>0?a:0-a)?sum:ans;
                    }
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (second < third && nums[third] + nums[second] + nums[first] <= target) {
                    List list = new LinkedList();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    System.out.println(list);
                    int sum = nums[first] + nums[second] + nums[third];
                    int a = sum - target;
                    ans = (ans - target > 0?ans - target:target - ans) >(a>0?a:0-a)?sum:ans;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {-100,-98,-2,-1};
        int target = -100;
        Solution16 solution16 = new Solution16() {
            @Override
            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int n = nums.length;
                int best = 10000000;

                // 枚举 a
                for (int i = 0; i < n; ++i) {
                    // 保证和上一次枚举的元素不相等
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    // 使用双指针枚举 b 和 c
                    int j = i + 1, k = n - 1;
                    while (j < k) {
                        int sum = nums[i] + nums[j] + nums[k];
                        // 如果和为 target 直接返回答案
                        if (sum == target) {
                            return target;
                        }
                        // 根据差值的绝对值来更新答案
                        if (Math.abs(sum - target) < Math.abs(best - target)) {
                            best = sum;
                        }
                        if (sum > target) {
                            // 如果和大于 target，移动 c 对应的指针
                            int k0 = k - 1;
                            // 移动到下一个不相等的元素
                            while (j < k0 && nums[k0] == nums[k]) {
                                --k0;
                            }
                            k = k0;
                        } else {
                            // 如果和小于 target，移动 b 对应的指针
                            int j0 = j + 1;
                            // 移动到下一个不相等的元素
                            while (j0 < k && nums[j0] == nums[j]) {
                                ++j0;
                            }
                            j = j0;
                        }
                    }
                }
                return best;
            }
        };
        int i = solution16.threeSumClosest(nums, target);
        System.out.println(i);

    }
}
